informatik_rwthfandomcom_de-20200214-history
Fehler
Signale können zum einen durch falsche Synchronisation missinterpretiert werden. Diese Fehlerklasse kann durch die Synchronisationsmechanismen vermieden werden. Eine weitere Klasse sind Übertragungsfehler, die durch Störeinflüsse auf dem Medium entstehen. Es wird zwischen Einzelbitfehlern und Fehlerbursts unterschieden. Im Unterschied zu Einzelbitfehlern, bei denen die Bits isoliert gestört sind, wirkt die Störung bei Bursts über mehrere Bits hinweg. Dabei müssen nicht zwangsläufig alle Bits fehlinterpretiert werden. Je höher die Datenrate des Mediums ist, desto wahrscheinlicher führen kurze Störimpulse zu Fehlerbursts statt Einzelfehlern. Ein passendes Maß ist die Bitfehlerrate (bit error rate, BER), welche aus dem Anteil der gestörten Bits zu den insgesamt übertragenen Bits besteht. Erkennung Eine einfache Form der Fehlererkennung besteht darin, ein Paritätsbit mitzuschicken, dass zur Prüfung der empfangenen Bits herangezogen werden kann. Ist die Summe der Bits, einschließlich des Paritätsbits, gerade, so wird von gerader Parität gesprochen. Wenn die Gesamtzahl der 1en ungerade ist hingegen von ungerader Parität. Die verschickten Bits werden zu Blöcken zusammengefasst, die beispielsweise 4 Bits lang sind. Es kann nun die Parität jedes Block gesichert werden, was als Block-''' oder '''Längsparität bezeichnet wird, oder es werden von z. B. immer 4 verschickten Blöcken die an der gleichen Stelle stehenden Bits geprüft, was Zeichen-''' oder '''Querparität genannt wird. Die Kombination von Längs- und Querparität nennt sich Kreuzsicherung. Ein Nachteil dieses Verfahrens ist, dass es nur für Einzelbitfehler geeignet ist. Denn zwei Fehler im gleichen Block (bzw. am gleichen Index bei der Querparität) lassen das Paritätsbit wieder korrekt erscheinen und werden nicht erkannt. Auch die Verwendung von Kreuzsicherung behebt das Problem bei Fehlerbursts nicht. Allerdings lassen sich Einzelbitfehler mit diesem Verfahren sogar beheben, da zwei Paritätsbits beeinflusst werden. Cyclic Redundany Check (CRC) Mit einem Cyclic Redundancy Check können beliebig lange Bitfolgen mit hoher Zuverlässigkeit auf Fehler überprüft werden. Hierzu wird den zu verschickenden Daten eine Frame Check Sequence (FCS) angehangen. Das Verfahren nutzt ein vereinbartes Generatorpolynom und interpretiert die zu verschickende Bitfolge selbst als Polynom. Dieses wird um so viele 0en erweitert, wie der Grad des Polynoms ist. Anschließend wird diese Zahl durch das Generatorpolynom dividiert. Der Rest der Teilung bildet die FCS. Der Empfänger prüft seine Daten, indem er sie ebenfalls durch das Generatorpolynom teilt. Ist der Rest 0, so sind die Daten (mit hoher Sicherheit) korrekt übertragen worden. Sei Beispielsweise das Generatorpolynom x^4+x^3+1 gegeben. Dieses wird durch das Polynom 11001 dargestellt. Die zu sendende Bitfolge 110011 wird nun um 4 Nullen (dem Grad des Polynoms entsprechend) erweitert auf 110011\; 0000 . Eine Division ergibt \frac{110011\; 0000}{11001}=100001+1001 . Dieser Rest 1001 bildet die FCS und wird mitverschickt. Der Empfänger teilt die Sequenz 110011\; 1001 durch das Generatorpolynom und erhält \frac{110011\; 1001}{11001}=100001+0 . Da der Rest 0 ist, wurden die Daten (wahrscheinlich) korrekt übertragen. Auch bei CRC können bestimmte Fehlerkonstellationen, ähnlich wie bei der Paritätsprüfung, nicht erkannt werden. Allerdings ergeben sich bei geeigneter Wahl des Generatorpolynoms Erkennungsraten in der Größenordnung 99,997%. Es gibt eine Menge international genormter Generatorpolynome. Behebung Durch Einführung von Redundanzen können Fehler behoben werden. Hierzu kann z. B. eine Prüfsumme eingesetzt werden. Es wird immer eine bestimmte Anzahl an Blöcken mit einem weiteren Prüfblock versehen, der sich aus der XOR-Verknüpfung der Bits mit gleichem Index aus allen Blöcken ergibt. Wird jeder Block mit einer FCS versehen (z. B. mittels CRC), so kann ein fehlerhafter Block erkannt und mittels XOR-Verknüpfung der anderen Blöcke wieder rekonstruiert werden. Hamming-Code Der Hamming-Code erzeugt Paritätsbits auf eine Weise, die die Fehlerkorrektur der Nachricht erlaubt. Jeder Index, der eine Zweierpotenz ist, stellt ein solches Paritätsbit dar. Jede natürliche Zahl ist durch Zweierpotenzen darstellbar. Dies wird ausgenutzt, indem jedes Paritätsbit für alle Stellen zuständig ist, in deren Zweierpotenzdarstellung der eigene Index auftaucht. So ist das Paritätsbit an Index 2 also für die Bits an Stelle 3(=''2''+1), 6=(4+''2''), 7(=4+''2''+1) usw. verantwortlich. Es ist zu beachten, dass 4 selbst eine Zweierpotenz ist, also 2 nicht noch die 4 abdeckt. Ebenso ist die 2 nicht für 5(=4+1) zuständig. Die Paritätsbits berechnen sich aus der Parität all dieser Bits, für die sie zuständig sind. Zur Erkennung eines Fehlers müssen die Paritätsbits der erhaltenen Nachricht durch erneute Bestimmung geprüft werden. Unterscheiden sich Paritätsbits, so lässt sich die fehlerhafte Stelle häufig erkennen. Sie ist nämlich diejenige, die sich aus den Indizes der fehlerhaften Paritätsbits ergibt. Sind z. B. die neu berechneten Paritätsbits 2 und 4 anders als die übertragenen Paritätsbits 2 und 4, so muss an der Stelle 6(=4+2) ein Fehler aufgetreten sein. Ist nur ein Paritätsbit falsch, so ist genau dieses Paritätsbit falsch übertragen worden. Ein derart erkannter Fehler lässt sich beheben, indem er aus der Parität aller für ihn zuständigen Paritätsbits rekonstruiert wird. Z. B. lässt sich ein fehlerhaftes Bit an Index 7(=4+2+1) korrigieren, indem es aus den übertragenen Paritätsbits 4, 2 und 1 errechnet wird. Auch beim Hamming-Code führen mehrere Fehler möglicherweise dazu, dass der Code sie nicht erkennt. Nützlich zur Beschreibung ist der Begriff des Hamming-Abstands als die Anzahl an Stellen, in denen sich zwei Wörter (hier Bitsequenzen) unterscheiden. Um Fehler erkennen und beheben zu können, muss der Hamming-Abstand eine bestimmte Größe übersteigen. * Um t Fehler zu erkennen, muss der Hamming-Abstand D mindestens D\geq t+1 betragen. * Um t Fehler zu beheben, muss der Hamming-Abstand D mindestens D\geq 2\cdot t+1 betragen. Um die oben genannten Hamming-Abstände zu garantieren, müsste ein einzelnes Bit zur Fehler''erkennung'' durch zwei Bits kodiert werden und zur Fehler''behebung'' durch drei. Beispielweise könnte zur Erkennung eine 0 als 00 und eine 1 als 11 kodiert werden, sodass ein einzelner Fehler erkannt werden kann. Denn ein einzelner Fehler würde entweder 10 oder 01 ergeben, sodass die Wörter nicht mehr dekodiert und als fehlerhaft erkannt werden könnten. Zur Fehler'behebung' sind drei Kodierungsbits nötig, also 0 als 000 und 1 als 111. Dann kann ein einzelner Bitfehler auch behoben werden, denn 100, 010 oder 100 muss offensichtlich aus 000, also 0 entstanden sein. Analog können - falls nur ein Bitfehler aufgetreten ist - 011, 101 und 110 eindeutig zu 111 und damit zu 1 zugeordnet werden. Da der Hamming-Code einen Hamming-Abstand von 3 aufweist, lassen sich bis zu 2 Bitfehler erkennen und einzelne Bitfehler korrigieren. Behandlung Statt dem Empfänger eine direkte Korrektur von Fehlern zu ermöglichen, kann auch dafür gesorgt werden, dass bei erkannten Fehlern die betroffenen Rahmen erneut verschickt werden. Dies wird durch Sendewiederholungsverfahren realisiert. Die Mechanismen, mit denen die Neubeantragung eines Rahmens implementiert wird, heißen ''a''utomatic ''r''epeat re''q''uests (ARQ). Manchmal sind solche Mechanismen nicht notwendig. Bei der Übertragung von beispielsweise Audioinformationen spielen einzelne, verlorene oder fehlerhafte Rahmen keine große Rolle und werden einfach ignoriert. Es besteht dann eine dauernde Übertragung vom Sender zum Empfänger. Stop-and-Wait Ein einfaches Verfahren bildet Stop-and-Wait, indem der Sender zu jedem versendeten Rahmen erst eine Bestätigung (engl. acknowledge, ACK) abwartet. Dieses ACK versendet der Empfänger bei dem Erhalt einer Nachricht. Erkennt der Empfänger einen Fehler im Rahmen, versendet er ein negatives ACK (NACK), sodass der Sender den Rahmen erneut verschickt. Wenn ein Paket auf dem Medium verloren geht und nie beim Empfänger ankommt, versendet dieser auch kein ACK oder NACK. Um diesem Problem verzubeugen, implementiert der Sender ein Timeout. Er wartet eine bestimmte Zeit nach dem Verschicken eines Rahmens. Ist diese Zeit abgelaufen, geht er davon aus, dass der Rahmen verloren gegangen ist und sendet ihn erneut. Daher muss der Timout mit Bedacht festgelegt werden, um zu verhindern, dass unnötig Rahmen mehrfach verschickt werden. Er muss über der zweifachen Latenz liegen, also der Zeit, in der ein ACK frühestens zurückkommt. Außerdem muss jeder Rahmen mit einer Sequenznummer versehen werden. Andernfalls würde, wenn das ACK zu einem Rahmen verloren geht, der Sender diesen Rahmen erneut senden. Da der Empfänger ihn bestätigt hat, würde er annehmen, es handele sich um einen neuen Rahmen, was zu Fehlinterpretation führt. Um zu erkennen, dass ein Rahmen erneut eintrifft, sind Sequenznummern notwendig. Neben der Fehlerbehandlung ist ein weiterer Vorteil dieses Verfahrens, dass der Empfänger nicht durch zu viele Rahmen hintereinander überlastet werden kann. Denn er kontrolliert mit seinem ACK, wann neue Rahmen verschickt werden. Ein Nachteil hingegen ist die geringe Effizienz, da durch die langen Wartezeiten die Datenrate des Mediums nicht genutzt wird. Go-Back-N Dieses Verfahren bestätigt stets den letzten, korrekt empfangenen Rahmen. Trifft ein fehlerhafter Rahmen ein, so wird das ACK wieder zum letzten korrekten verschickt. Alle weiteren eintreffenden Rahmen, egal ob sie fehlerfrei sind, werden immer wieder mit diesem ACK quittiert. Diese ermöglicht dem Sender an mehrfach eintreffenden ACKs zu erkennen, dass ein Fehler eingetreten ist. Sobald also ein doppeltes ACK eintrifft, sendet er alle Rahmen ab der zum ACK gehörenden Sequenznummer erneut. Es gibt Varianten dieses Verfahrens. Zum einen kann bei fehlerhaften Rahmen ein NACK versendet werden, das den Sender direkt auffordert, alle Rahmen ab einer bestimmten Sequenznummer erneut zu senden. Die andere Möglichkeit bedient sich eines Timeouts. Hierbei wird auf fehlerhafte Rahmen nicht reagiert. Der Sender versendet die betroffenen Rahmen erneut, nachdem der Zeitzähler für einen Rahmen abgelaufen ist und dieser als verloren angenommen wird. Dieses Verfahren eignet sich nur für Medien mit geringer Latenz und Datenrate. Sonst könnten in der Zeit, bis der Sender vom Fehler erfährt, bereits sehr viele korrekte Rahmen übertragen worden sein, die nun unnötig erneut verschickt würden. Selective Repeat Dieses Verfahren forder daher fehlerhafte Rahmen explizit erneut an, indem es korrekte durch ein ACK bestätigt und fehlerhafte durch ein NACK anfordert. Trifft ein solches NACK beim Sender ein, wiederholt er nur den entsprechenden Rahmen. Der Empfänger, nachdem diese Rahmen korrekt bei ihm eingetroffen ist, quittiert alle bisher korrekt erhaltenen Rahmen zusammen durch ein ACK mit der Sequenznummer des höchsten davon. Eine Variante ist die implizite Übertragungswiederholung, bei der ein Timeout beim Sender für die Neusendung von Rahmen folgt, da der Empfänger hier nur den letzten korrekt empfangenen Rahmen quittiert. Ein Nachteil ist, dass nach der Neuversendung eines Rahmens erst das ACK des Empfängers für alle erhaltenen Rahmen eintrifft. In dieser Zeit können die Timeouts für Folgerahmen ablaufen, sodass diese neu verschickt werden, obwohl sie bereits beim Empfänger angekommen waren. Daher ist dieses Verfahren dem expliziten unterlegen. Flusskontrolle Der Empfänger hat nur begrenzten Speicherplatz zur Annahme von Rahmen zur Verfügung, kann daher bei den beiden letzten Verfahren durch zu viele Rahmen überlastet werden. Um dies zu verhindern, wird Flusskontrolle (auch Flusssteuerung oder -regulierung) eingesetzt. Die simpelste Methode ist das Verschicken von Halt-Nachrichten durch den Empfänger, wenn dieser zu überlasten droht. Sobald er wieder bereit ist, signalisiert er dies dem Sender durch eine Weiter-Nachricht. Dennoch kann hier Überlastung auftreten, wenn die Latenz so groß ist, dass die Halt-Nachricht zu spät eintrifft und der Sender bereits zu viele Rahmen versendet hat. Daher setzt das Sliding Window-Verfahren ein Übertragungsfenster ein, das durch die Größe des Empfängerspeichers beschränkt ist. Eine Fenstergröße w bedeutet, dass der Empfänger höchstens w Nachrichten auf einmal verarbeiten kann. Der Sender nummeriert seine Nachrichten mit Zahlen durch, die Modulo einer Zahl größer als w genommen werden. Dies garantiert, dass die Rahmen im Fenster stets eindeutig nummeriert sind und keine Verwechslung zu dem nächsten zu verschickenden auftreten kann. Der Empfänger bestätigt die korrekt empfangenen Rahmen, die der Sender aus seinem Sendefenster herauslöscht. Er verschickt nun die folgenden Rahmen, bis das Fenster wieder voll ist. Eine Art der Veranschaulichung besteht mit Kredit. Zunächst muss der Empfänger die zur Verfügung stehende Fenstergröße bestimmen und gibt damit dem Sender bildlich einen Kredit. Jede Nachricht des Senders verbraucht einen Kreditpunkt, sodass er nur so viele Rahmen versendet, wie in das Fenster passen. Bei Erhalt einer Nachricht, bestätigt der Empfänger diese und überträgt dem Sender somit einen Kreditpunkt. Nun kann der Sender also pro erhaltenem Kreditpunkt eine weitere Nachricht schicken. Referenzen Wenn nicht anders angegeben, stammt der Inhalt aus den Vorlesungsfolien: * Meyer, U.: Vorlesungsfolien "20160428-SS-DatKom-3-Sicherungsschicht" ( ) Siehe auch Übersichtsseite von Datenkommunikation und Sicherheit